//LCR 015. 找到字符串中所有字母异位词


#include <vector>
#include <string>
using namespace std;

class Solution
{
public:
    vector<int> findAnagrams(string s, string p) 
    {
        vector<int> ret;
        int hash1[26] = { 0 };
        for(auto ch : p) hash1[ch - 'a']++; // 统计p中的每个字符出现的个数

        int hash2[26] = { 0 }; // 统计窗口里每个字符出现的个数
        int n = p.size();
        for(int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            char in = s[right];
            hash2[in - 'a']++; // 进窗口
            if(hash2[in - 'a'] <= hash1[in - 'a']) count++; // 维护 count
            if(right - left + 1 > n) // 判断
            {
                char out = s[left++];
                if(hash2[out - 'a'] <= hash1[out - ' a']) count--; // 维护 count
                hash2[out - 'a']--; // 出窗口
            }
            if(count == n) ret.push_back(left);
        }
        return ret;
    }
};